`
https://leetcode.cn/problems/interleaving-string/
`

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
  const m = s1.length, n = s2.length, t = s3.length;
  if (m + n !== t) return false;

  // 创建 (m+1)x(n+1) 的DP表格
  const dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(false));

  // 初始条件：空字符串可以组成空字符串
  dp[0][0] = true;

  // 初始化第一列：只用s1的情况
  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  }

  // 初始化第一行：只用s2的情况
  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
  }

  // 填充DP表
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const k = i + j; // s3中的位置

      // 两种情况满足其一即可：
      // 1. 当前字符来自s1，且之前的部分也有效
      const fromS1 = dp[i - 1][j] && s1[i - 1] === s3[k - 1];

      // 2. 当前字符来自s2，且之前的部分也有效
      const fromS2 = dp[i][j - 1] && s2[j - 1] === s3[k - 1];

      dp[i][j] = fromS1 || fromS2;
    }
  }

  return dp[m][n];
};

// test
console.log(isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
console.log(isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
console.log(isInterleave("", "", "")); // true